package reviewAlgorithms.dynamicProgramming;

public class MinSteps {
    public static void main(String[] args) {
        int n = 10;
        System.out.println(minStepsDiGui(n));
        System.out.println(minStepsDP(n));
    }

    private static int minStepsDP(int n) {
        if (n < 1){
            return 0;
        }
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = 2; j <= Math.sqrt(n); j++) {
                if (i % j == 0){
                    dp[i] = j + dp[i/j];
                }
            }
        }
        return dp[n];
    }

    public static int minStepsDiGui(int n) {
        if (n < 1){
            return 0;
        }
        if (n == 1){
            return 1;
        }
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0){
                return i + minStepsDiGui(n/i);
            }
        }
        return n;
    }

}
